
//918.环形子数组的最大和
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();

        int sum = accumulate(nums.begin() ,nums.end() ,0);
        vector<int> f(n+1) ,g(n+1);     //f记录以i为结尾的最大值 , g记录以i位置为结尾的最小值
        int ret =INT_MIN;
        for(int i = 1 ; i < n + 1 ;i++)
        {
            f[i] = max(f[i-1] + nums[i-1] ,nums[i-1]);
            g[i] = min(g[i-1] + nums[i-1] ,nums[i-1]);

            ret = max(ret, f[i]);
            if(sum != g[i]) ret = max(ret,sum-g[i]);
        }
        return ret;
    }
};